Dense meshes of interconnected data points are used to represent surfaces of arbitrary topology in numerous applications. For example, such meshes routinely result from three-dimensional data acquisition techniques such as laser range scanning and magnetic resonance volumetric imaging followed by surface extraction. These meshes are often configured in the form of a large number of triangles, and typically have an irregular connectivity, i.e., the vertices of the mesh have different numbers of incident triangles. Because of their complex structure and potentially tremendous size, dense meshes of irregular connectivity are difficult to handle in such common processing tasks as storage, display, editing, and transmission.
It is well known that multiresolution representations of dense meshes can be used to facilitate these processing tasks. A conventional approach used to generate such a representation is based on sequential mesh simplification, e.g., progressive meshes (PM), as described in, for example, H. Hoppe, “Progressive meshes,” in Computer Graphics (SIGGRAPH '96 Proceedings), pp. 99-108, 1996. Other mesh simplification techniques are described in, e.g., A. Lee et al., “MAPS: Multiresolution Adaptive Parameterization of Surfaces,” Computer Graphics (SIGGRAPH '98 Proceedings), pp. 95-104, 1998; P. S. Heckbert and M. Garland, “Survey of polygonal surface simplification algorithms,” Tech. Rep., Carnegie Mellon University, 1997; and M. Eck et al., “Multiresolution analysis of arbitrary meshes,” in Computer Graphics (SIGGRAPH '95 Proceedings), pp. 173-182, 1995.
The basic objective of classical multiresolution analysis and mesh simplification is to represent meshes in an efficient and flexible manner, and to use this representation in algorithms which address the processing challenges mentioned above. An important element in the design of such algorithms is the construction of “parameterizations,” i.e., functions mapping points on a coarse “base domain” mesh to points on a finer original mesh. Once a surface is characterized in this manner, as a function between a base domain and a space of three or more dimensions, many techniques from fields such as approximation theory, signal processing, and numerical analysis may be used to process data representing the surface.
In the case of regularly sampled data, e.g., images, basic signal processing tools such as upsampling, downsampling and filtering exist. These can be used to build subdivision and pyramid algorithms, which are useful in many applications. For example, images are functions defined on Euclidean, i.e., “flat,” geometry and are almost always sampled on a regular grid. Consequently, algorithms such as upsampling and downsampling are straightforward to define, and uniform filtering methods are appropriate. This makes Fourier analysis an elegant and efficient tool for the construction and analysis of signal processing algorithms.
In contrast, meshes of arbitrary connectivity form an inherently irregular sampling setting. Additionally, we are dealing with general 2-dimensional manifolds (2-manifolds), possibly with boundaries, as opposed to a Euclidean space. Consequently new algorithms need to be developed which account for the fundamental differences between images and meshes.
A crucial first observation concerns the difference between geometric and parametric smoothness. Geometric smoothness measures how much triangle normals vary over the mesh. Geometric smoothness implies that there exists some smooth, i.e., differentiable, parameterization of the mesh. However, any particular parameterization may well be non-smooth. The smoothness of the parameterizations is important in most numerical algorithms, which work only with the coordinate functions the user provides. The algorithms' behavior, such as convergence rates or the quality of the results, generally depend strongly on the smoothness of the coordinate functions. In the regular setting of an image, or the knots of a uniform tensor product spline, we may simply use a uniform parameterization and will get parametric smoothness wherever there is geometric smoothness. However, in the irregular triangle mesh setting there is a priori no such obvious parameterization. In this case, using a uniformity assumption leads to parametric non-smoothness with undesirable consequences for further processing.
One possible approach to remedy this situation is the use of remeshing in accordance with the techniques in the above-cited A. Lee et al. reference. This approach maintains the original geometric smoothness, but improves the sampling to vary smoothly, thereby enabling subsequent treatment with a uniform parameter assumption without detrimental effects. However, a need still remains for signal processing tools which can work on the original meshes directly.
It should be noted that triangle meshes, also referred to as triangulations, may be of a number of different types, including regular, in which every vertex has degree six; irregular, in which vertices can have any degree; and semi-regular, which are formed by starting with a coarse irregular triangulation and performing repeated quadrisection on all triangles. For semi-regular meshes, coarse vertices are assumed to be of arbitrary degree while all other vertices are assumed to be of degree six. In all cases, we assume that any triangulation is a proper 2-manifold with boundary. On the boundary, regular vertices have degree four. It should also be noted that each of the above-noted triangulations generally utilize different filtering and subdivision algorithms. More particularly, uniform algorithms use so-called fixed coefficient stencils and are typically used only on regular triangulations. In non-uniform algorithms, filter coefficients depend on the connectivity and geometry of the triangulation. Semi-uniform algorithms use filter coefficients which depend only on the local connectivity of the triangulation, and are typically used on semi-regular triangulations.
In order to understand further the role of the parameterization, consider conventional subdivision, such as Loop or Catmull-Clark, as described in, e.g., P. Schröder and D. Zorin, Eds., “Course Notes: Subdivision for Modeling and Animation,” ACM SIGGRAPH, 1998. In the signal processing context, subdivision can be seen as upsampling followed by filtering. One starts with an arbitrary connectivity mesh and uses regular upsampling techniques such as triangle quadrisection to obtain a semi-regular triangulation. The subdivision weights depend only on connectivity, not geometry. Such stencils can be designed with existing Fourier or spectral techniques. These techniques result in geometrically smooth limit surfaces with smooth, semi-uniform parameterizations. Because traditional subdivision is only concerned with refinement, one has the freedom to choose regular upsampling, and semi-uniform schemes suffice.
The situation is different if we wish to compute a mesh pyramid, i.e., we want to be able to coarsify a given fine irregular mesh and later refine it again. We then need to filter, downsample, upsample and filter again. The downsampling typically involves a standard mesh simplification hierarchy. When subdividing back, we want to build a mesh with the same connectivity as the original mesh and a smooth geometry. This time the upsampling procedure is determined by reversing the previously computed simplification hierarchy. However, we no longer have the choice as to where to place the new vertices that we had in the classical subdivision setting. Consequently, the filters used before downsampling and after upsampling should use non-uniform weights, which depend on the local parameterization. The challenge is to ensure that these local parameterizations are smooth so that subsequent algorithms act on the geometry and not some potentially undesirable parameterization.
Signal processing as an approach to surface fairing in the irregular connectivity mesh setting has been described in G. Taubin, “A Signal Processing Approach to Fair Surface Design,” Computer Graphics (SIGGRAPH '95 Proceedings), pp. 351-358, 1995, and G. Taubin, T. Zhang and G. Golub, “Optimal Surface Smoothing as Filter Design,” Tech. Rep. 90237, IBM T. J. Watson Research, March 1996. This approach defines frequencies as the eigenvectors of a semi-uniform discrete Laplacian L generalized to irregular triangulations. It utilizes a two step relaxation operator R=(I+μL)(I+λL), with μ and λ tuned to minimize shrinkage of the mesh. The resulting smoothing schemes have been used to denoise meshes, to apply smooth deformations, and to build semi-uniform subdivision over irregular meshes. However, such an approach can introduce triangle distortions, and it is not linearly invariant, i.e., when applied to an irregularly-triangulated plane, it introduces tangential movement, also known as movement “within” a surface.
The use of progressive meshes and a semi-uniform discrete Laplacian to perform multiresolution editing on irregular meshes is described in L. Kobbelt, S. Campagna, J. Vorsatz and H.-P. Seidel, “Interactive Multi-resolution Modeling on Arbitrary Meshes,” Computer Graphics (SIGGRAPH '98 Proceedings), pp. 105-114, 1998. Given some region of the mesh, discrete fairing is used to compute a smoothed version with the same connectivity. This smoothed region is deformed, and offsets to the original mesh, in the form of so-called detail vectors, are subsequently added back in.
This approach assumes that the 1-ring neighborhood of a given vertex i of the mesh is parameterized over a regular Ki-gon. Using this approximation, a semi-uniform discrete Laplacian, referred to as an “umbrella,” is computed asLpi=Ki−1Σjεv1(i)pj−pi This discrete Laplacian is then used in a relaxation operator R=I+L which replaces a vertex with the average of its 1-ring neighbors.
However, smoothing of irregular meshes based on uniform approximations of the Laplacian results in vertex motion “within” the surface, even in a perfectly planar triangulation. Although geometrically smooth, the parameter functions appear non-smooth due to a non-uniform parameterization. This has undesirable effects in a hierarchical setting in which fine levels are defined as offsets from a coarse level. More particularly, using the difference between topologically corresponding vertices in the original and smoothed mesh can lead to detail vectors with large tangential components. To minimize the size of the tangential components of the detail vectors, a search procedure is used to find the nearest vertex on the smoothed mesh to a given vertex on the original mesh. However, this diminishes the advantage of having a smoothed version with the exact same connectivity.
As is apparent from the above, a need exists for an improved mesh relaxation procedure which is linearly invariant, and which can be used as the basis for implementing multiresolution signal processing operations such as upsampling, downsampling and filtering on irregular connectivity meshes, while avoiding the problems associated with the above-described conventional techniques.